In network equipments, a Ternary Content Addressable Memory (TCAM) is widely used due to its fast search characteristics. For example, it is used for fast route search, Access Control List (ACL) search, stream-based Quality of Service (QOS), policy-based routing and various safety techniques. In network equipments, a certain content of a message is usually used as an input for the search by the TCAM. The TCAM compares the input with all table entries stored therein, and when a completely matched table entry is found, executes an action bound to the table entry, e.g., discarding the message, allowing to forward the message, or modifying certain information of the message. When a plurality of table entries are completely matched with the input, the headmost one will be taken.
For example, in the application of route prefix search, a destination IP address of an input message is taken as the content to be inputted to the TCAM to search information related to the next hop. Other applications have similar processes. For another example, in the application of ACL search, the user sets “Permit ip host 192.168.1.1; Deny ip any any” and binds it to a port. When the port receives a message, it will extract an input port of the message, a field of protocol type, and a source IP address as the contents to be input to the TCAM for a search. When the message is of IP type and the source IP address is 192.168.1.1, the related TCAM table entry “permit ip host 192.168.1.1” will be hit, and a “permit” action will be executed, i.e., forwarding is allowed; otherwise a “deny” action will be executed for all other messages, i.e., all other messages will be discarded.
Whether the TCAM is used for fast route search or an application such as ACL search, etc., a certain order of the table entries of the TCAM will typically be maintained, i.e., the table entries have a fixed priority relationship thereamong and are stored in a continuous space. The table entries of the TCAM will be continuously updated during the operation of the equipment.
In the prior art methods for updating table entries of the TCAM, when the TCAM contains many table entries, as shown in FIG. 1, in case that a table entry needs to be added between Table Entries 3 and 4, while there is no continuous hardware space of an appropriate size between Table Entries 3 and 4, other table entries may be moved upwards and/or downwards. The addition of one table entry may cause rewriting of a lot of other table entries, which leads to a low efficiency in updating the table entries.